//package com.zjsru.oneDay;
//
//import java.util.Arrays;
//import java.util.PriorityQueue;
//
///**
// * 3342. 到达最后一个房间的最少时间 II
// * @Author: cookLee
// * @Date: 2025-05-08
// */
//public class MinTimeToReach {
//
//    /**
//     * 主
//     * \
//     * 给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为：第一次花费 1 秒，第二次花费 2 秒，第三次花费 1 秒，第四次花费 2 秒……如此 往复 。
//     * \
//     * 输入：moveTime = [[0,4],[4,4]]
//     *
//     * 输出：7
//     *
//     * 解释：
//     *
//     * 需要花费的最少时间为 7 秒。
//     *
//     * 在时刻 t == 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
//     * 在时刻 t == 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 2 秒。
//     * \
//     * 输入：moveTime = [[0,0,0,0],[0,0,0,0]]
//     *
//     * 输出：6
//     *
//     * 解释：
//     *
//     * 需要花费的最少时间为 6 秒。
//     *
//     * 在时刻 t == 0 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
//     * 在时刻 t == 1 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 2 秒。
//     * 在时刻 t == 3 ，从房间 (1, 1) 移动到房间 (1, 2) ，花费 1 秒。
//     * 在时刻 t == 4 ，从房间 (1, 2) 移动到房间 (1, 3) ，花费 2 秒。
//     * \
//     * @param args args
//     */
//    public static void main(String[] args) {
//        MinTimeToReach minTimeToReach = new MinTimeToReach();
//        System.out.println(minTimeToReach.minTimeToReach(new int[][]{{0,4},{4,4}}));
//    }
//
//    private final static int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
//
//    public int minTimeToReach(int[][] moveTime) {
//        int len = moveTime.length;
//        int colLen = moveTime[0].length;
//        int[][] visited = new int[len][colLen];
//        for (int[] row : visited) {
//            Arrays.fill(row, Integer.MAX_VALUE);
//        }
//        visited[0][0] = 0;
//
//        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
//        queue.add(new int[]{0, 0, 0});
//        while (true) {
//            int[] poll = queue.poll();
//            int d = poll[0];
//            int x = poll[1];
//            int y = poll[2];
//            if (x == len - 1 && y == colLen - 1) {
//                return d;
//            }
//            if(d > visited[x][y]){
//                continue;
//            }
//            int time = (x + y) % 2 + 1;
//            for (int[] q : DIRS) {
//                int newX = x + q[0];
//                int newY = y + q[1];
//                if (newX >= 0 && newX < len && newY >= 0 && newY < colLen ) {
//                    int newTime = Math.max(d , moveTime[newX][newY]) + time;
//                    if(newTime < visited[newX][newY]){
//                        visited[newX][newY] = newTime;
//                        queue.add(new int[]{newTime, newX, newY});
//                    }
//                }
//            }
//        }
//    }
//}
